/**
 * @file 最长递增子序列
 */

const mockArr = [ 10, 9, 2, 5, 3, 7, 101, 18 ];

/**
 * 动态规划
 * @param arr
 */
function lengthOfLIS(arr) {
    const dp = Array(arr.length).fill(1);
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                console.log(dp);
            }
        }
    }
    let res = 0;
    for (let i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i])
    }
}

// lengthOfLIS(mockArr);

/**
 * 贪心 + 二分
 */
function _lengthOfLIS(arr) {
    let top = [],
        piles = 0;
    for (let i = 0; i < arr.length; i++) {
        let poker = arr[i],
            left = 0,
            right = piles;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        console.log(top);
        if (left === piles) piles++;
        top[left] = poker
    }
    return piles;
}

console.log(_lengthOfLIS(mockArr));

